package lee.meiriyiti.day1116;

public class TestDemo1116_2 {//求第k大，快排思想
    //https://www.nowcoder.com/questionTerminal/e016ad9b7f0b45048c58a9f27ba618bf
    public static int findKth(int[] array, int K) {
        return quick(array, 0, array.length - 1, K);
    }

    private static int quick(int[] array, int low, int high, int K) {
        int par = partition(array, low, array.length - 1);
        if (K < par + 1) {
            return quick(array, low, par - 1, K);
        } else if (K > par + 1) {
            return quick(array, par + 1, high, K);
        } else
            return array[par];
    }

    private static int partition(int[] array, int low, int high) {//求中间位置
        int tmp = array[low];
        while (low < high) {
            while (low < high && array[high] <= tmp) {
                high--;
            }
            array[low] = array[high];
            while (low < high && array[low] >= tmp) {
                low++;
            }
            array[high] = array[low];
        }
        array[low] = tmp;
        return low;
    }

    public static void main(String[] args) {
        int[] array = {1, 7, 3, 9, 2, 6, 4};
        System.out.println(findKth(array, 1));
    }
}
